﻿//一道题的测试
//#define _CRT_SECURE_NO_WARNINGS
//#include<iostream>
//using namespace std;
//
//class A
//{
//public:
//    A():
//        m_iVal(0)    //第三步
//    {         //第二步跳到这里
//        test();    //第四步
//    }  //第八步
//     
//    virtual void func() 
//    {    //第六步
//        cout << m_iVal <<' '; 
//    }
//    void test() 
//    {   //第五步      转跳到了第十步        十五部
//        func();  
//    }  //第七步        十二步
//
//public:
//    int m_iVal;
//};
//
//class B : public A
//{
//public:
//    B()     //第一步调用这个        第九步跳回
//    { 
//        test();    //到这转跳到第十步
//    }     //十三步
//    
//    virtual void func()
//    {      //十一步      十六步
//        ++m_iVal;
//       cout << m_iVal << ' ';
//    }
//};
//
//int main(int argc, char* argv[])
//{
//    A* p = new B;   //构造对象
//    p->test();    //十四步
//    return 0;
//}

/*
序列式容器和关联式容器
	STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，
	因为逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，
	他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

	关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，
	两个位置有紧密的关联关系，交换一下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来
	保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列（非线性   哈希表）。

	map和set底层是红黑树   红黑树是一棵平衡二叉搜索树   set是key搜索场景的结构
	map是key/value搜索场景的结构


set的两个容器
set（key场景） 和 multiset（多样set 允许键值冗余）

set的声明，T就是set底层关键字的类型：
	template < class T,					// set::key_type/value_type
	 class Compare = less<T>,			// set::key_compare/value_compare
	 class Alloc = allocator<T>			// set::allocator_type
	 > class set;

注意：
	1.set默认要求T支持⼩于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模
版参数（T用K更适合）
	2.set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参
数。
	3.一般情况下，都不需要传后两个模版参数。
	4.set底层是用红黑树实现,增删查效率是O(logN),迭代器遍历是走的搜索树的中序,所以是有序的。
	  C++时间复杂度无论log以谁为底都是 O(logN)


multiset 和 set的差异
	multiset和set的使用基本完全类似，区别在于multiset支持值冗余，insert/find/count/erase都围绕着支持值冗余有所差异
	multiset头文件也是set



map（insert一个pair）
	map有两个模板参数  key_value  的容器
	支持增删查改    支持修改value
	
	key_type ---> key
	mapped_type ---> T
	value_type ---> pair<const key_type,mapped_type>

	pair是模板   两个模板参数

map的删除只和key有关
	emplace类似insert的功能

map的operator[]  有三种功能
	插入   查找    修改

map的insert （充当插入和查找的功能）
	插入成功   返回pair<新插入值所在迭代器，true>
	插入失败   返回pair<已经存在的跟key相等的值节点的所在迭代器，false>

map的  operator的内部实现
	mapped_type& operator[] (const key_type& k)
	{
		pair<iterator,bool> ret = insert({k,mapped_type()});
	*	iterator it =ret.first;   *
		return it->second;
	}

 * 这里的iterator 有两层    实际里面是 Node* ---> pair<K,V> (key_value的pair)    ret的first就是key   second就是value    


	str不存在   插入+修改
	str存在     查找+修改

	1、如果k不在map中，insert会插入k和mapped_type默认值，同时[]返回结点中存储
mapped_type值的引用，那么我们可以通过引用修改返映射值。所以[]具备了插入+修改功能
	2、如果k在map中，insert会插入失败，但是insert返回pair对象的first是指向key结点的
迭代器，返回值同时[]返回结点中存储mapped_type值的引用，所以[]具备了查找+修改的功能


multimap  允许键值冗余（允许有相同的内容）
	譬如：multimap<string,string> dict
		  dict.insert({"sort","排序"});
		  dict.insert({"sort","排序"});
		  dict.insert({"sort","排序"});
		  dict.insert({"sort","排序"});
区别于map的一点：不支持  []

*/
